package com.fang.offer.linked;

/**
 * <pre>
 * 题目描述
 * 输入一个链表，输出该链表中倒数第k个结点。
 * </pre>
 *
 */
public class OfferFindKthToTail {

	public static void main(String[] args) {
		ListNode root = new ListNode(1);
		root.next = new ListNode(2);
		root.next.next = new ListNode(3);
		root.next.next.next = new ListNode(4);
		root.next.next.next.next = new ListNode(5);

		ListNode root2 = new ListNode(1);

		ListNode root3 = null;

		System.out.println(OfferFindKthToTail.findKthToTail(root, 6));
		System.out.println(OfferFindKthToTail.findKthToTail(root, 7));
		System.out.println(OfferFindKthToTail.findKthToTail(root2, 1));
		System.out.println(OfferFindKthToTail.findKthToTail(root2, 0));
		System.out.println(OfferFindKthToTail.findKthToTail(root3, 6));

	}

	public static ListNode findKthToTail(ListNode head, int k) {
		if ((head == null) || (k <= 0))
			return null;
		ListNode previous = head;
		ListNode behind = null;
		for (int i = 0; i < (k - 1); i++) {
			if (previous.next == null)
				return behind;
			previous = previous.next;
		}

		behind = head;
		while (previous.next != null) {
			previous = previous.next;
			behind = behind.next;
		}

		return behind;

	}
}
